package fun.coding.leetcode;

public class MaximumSubarray {

	public static void main(String[] args) {
		
		int[] a = {-2,1, -3,4,-1,2,1, -5,4};
		int[] b = {-2, -2};
		int[] c = {-2, 5, 8};
		int[] d = {-2, 5, 8, 10};
		MaximumSubarray ms = new MaximumSubarray();
		System.out.println(ms.maxSubArray(a));
		System.out.println(ms.maxSubArray(b));
		System.out.println(ms.maxSubArray(c));
		
		System.out.println("max sub every other one");
		System.out.println(ms.maxSubArrayEveryOther(a));
		System.out.println(ms.maxSubArrayEveryOther(b));
		System.out.println(ms.maxSubArrayEveryOther(c));
		System.out.println(ms.maxSubArrayEveryOther(d));
	}
	// * dp[n] = max(array[n], dp[n-1] + array[n])
    public int maxSubArray(int[] A) {
    	if (A == null || A.length == 0) {
    		return 0;
    	}
    	
    	int pre = A[0];
    	int max = A[0];
    	
    	for (int i = 1; i < A.length; ++i) {
    		pre = Math.max(A[i], A[i] + pre);
    		max = Math.max(pre, max);
    	}
    	
    	return max;
    }
    
    public int maxSubArrayEveryOther(int[] A) {
    	if (A == null || A.length == 0) {
    		return 0;
    	}
    	int n = A.length;
    	int[] lookup = new int[n+1];
    	
    	lookup[0] = 0;
    	lookup[1] = A[0];
    	int max = Integer.MIN_VALUE;
    	for (int i = 2; i <= n; ++i) {
    		lookup[i] = Math.max(lookup[i-2] + A[i-1], A[i-1]);
    		if (lookup[i] > max) {
    			max = lookup[i];
    		}
    	}
    	
    	return max;
    }

}
